# 1590. 使数组和能被 P 整除
# 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

# 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

# 子数组 定义为原数组中连续的一组元素。

#  

# 示例 1：

# 输入：nums = [3,1,4,2], p = 6
# 输出：1
# 解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
# 示例 2：

# 输入：nums = [6,3,5,2], p = 9
# 输出：2
# 解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
# 示例 3：

# 输入：nums = [1,2,3], p = 3
# 输出：0
# 解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
# 示例  4：

# 输入：nums = [1,2,3], p = 7
# 输出：-1
# 解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
# 示例 5：

# 输入：nums = [1000000000,1000000000,1000000000], p = 3
# 输出：0
#  

# 提示：

# 1 <= nums.length <= 105
# 1 <= nums[i] <= 109
# 1 <= p <= 109


# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/make-sum-divisible-by-p
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from typing import List


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        x = sum(nums) % p
        if x == 0:
            return 0
        y = 0
        index = {0: -1}
        ans = len(nums)
        for i, v in enumerate(nums):
            y = (y + v) % p
            if (y - x) % p in index:
                ans = min(ans, i - index[(y - x) % p])
            index[y] = i
        return ans if ans < len(nums) else -1
    
    
if __name__ == '__main__':
    # args = {"nums": [3,1,4,2], "p": 6}
    # args = {"nums": [6,3,5,2], "p": 9}
    # args = {"nums": [1,2,3], "p": 3}
    args = {"nums": [1,2,3], "p": 7}
    # args = {"nums": [1000000000,1000000000,1000000000], "p": 3}
    start = time()
    print(Solution().minSubarray(**args))
    print('='*40)
    print('耗时:', time()*1000 - start*1000, 'ms')